Object oriented data base applications and hypertext systems users spend a significant amount of time processing a page, and the computer and I/O system are essentially idle during that period. If the computer system can predict which page the user will request next, it can fetch that page into cache if it is not already in cache before the user asks for it. Thus, when the user actually asks for the page, the page is available instantaneously, and the user perceives a faster response time. This method of anticipating and getting pages into cache in the background is called prefetching.
Database systems that perform prefetching using techniques derived from older virtual memory systems have I/O limitations that seriously impede performance in large scale databases. This has led to improved algorithms for prefetching, such as the pattern matching approach in U.S. Pat. No. 5,305,389 issued to Palmer (1994), first-order statistics by Salem, "Adaptive Prefetching for Disk Buffers," CESDIS, Goddard Space Flight Center, TR-91-64, (January 1991), and a growing order Markov predictor used by Laird, "Discrete Sequence Prediction and its Applications," AI Research Branch, NASA Research Center, (1992).
Data compression techniques used for predicting are discussed in several publications by the inventors. See "Optimal Prefetching via Data Compression," Brown University Tech Report No. CS-91-46, (1991), "Practical Prefetching via Data Compression," Proceeding of the ACM SIGMOD '93 Conference, (May 26-28, 1993), and "Optimal Prediction for Prefetching in the Worst Case," Duke University Technical Report CS-1993-26, (October 1993). The intuition is that data compressors typically operate by postulating a dynamic probability distribution on the data to be compressed. If a data compressor successfully compresses the data, then its probability distribution on the data must be realistic and can be used for effective prediction.
The process of converting character-based data compressors to pure prefetchers is relatively simple. However, there are practical issues in prefetching, in particular time and memory restrictions that have to be considered, which are not as significant in data compression.